package paixu;

/**
 * @author lj
 * @Description: 堆排-大根堆
 * @date 2020-11-01 15:59
 * @QQ 851477108
 */


public class heapSort {
    public static void main(String[] args) {
        int[] arr = {5,8,6,2,4,3,1,7,9,11};
        headSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public static void headSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        //先构建大顶堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }

        int size = arr.length;

        swap(arr,0, --size);

        while (size > 0){
            //维持大根堆结构
            heapify(arr,0,size);
            //每次选大顶堆root节点 size不断减1
            swap(arr,0,--size);
        }

    }

    public static void heapInsert(int[] arr, int index){
        //当前子节点大于父节点时，将两者交换
        //在完全二叉树中，大根堆父字节必比子节点大，交换是上下交换的形式
        while (arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            //从下往上交换，当index=0时停止
            index = (index-1)/2;
        }
    }

    public static void heapify(int[] arr, int parent, int size){
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;
        int max;
        while (left < size){
            //左右孩子都不越界，取出其中最大一个孩子的值largest
            max = right < size && arr[right] > arr[left] ? right : left;
            //比较父节点和最大子节点,取最大值
            max = arr[max] > arr[parent] ? max : parent;
            if (max == parent){
                break;//等于就退出
            }
            //交换父节点和最大的子节点
            swap(arr,max,parent);
            //以当前的父节点作为子节点继续遍历，直到叶子节点的无子节点为止
            parent = max;
            left = parent * 2 + 1;
            right = parent * 2 + 2;
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
